package queue;

import java.util.Iterator;
import java.util.Map;

/**
 * 仅用head,tail判断空满,head、tail需要换算成索引值
 *
 * @author yyz
 * @create 2023-11-27 19:05
 */
public class ArrayQueue3<E> implements Queue<E>, Iterable<E> {

    private final E[] array;
    /*private */ int head = 0;
    /*private */ int tail = 0;

    @SuppressWarnings("all")
    public ArrayQueue3(int capacity) {
        //判断capacity是否是2的幂
        //1. 抛异常
        /*if ((capacity & capacity-1)!=0) {
            throw new IllegalArgumentException("capacity 必须是2的幂");
        }*/
        //2. 改成 2^n
        //方法一
        /*int n = (int) (Math.log10(capacity - 1) / Math.log10(2) + 1);
        capacity = 1 << n;*/

        //方法二
        capacity -= 1;
        capacity |= capacity >>> 1;
        capacity |= capacity >>> 2;
        capacity |= capacity >>> 4;
        capacity |= capacity >>> 8;
        capacity |= capacity >>> 16;
        capacity += 1;

        array = (E[]) new Object[capacity];
    }

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            int p = head;

            @Override
            public boolean hasNext() {
                return p != tail;
            }

            @Override
            public E next() {
                E value = array[p & (array.length - 1)];
                p++;
                return value;
            }
        };
    }

    @Override
    public boolean offer(E value) {
        if (isFull()) {
            return false;
        }
        array[tail & (array.length - 1)] = value;
        tail++;
        return true;
    }

    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }
        E value = array[head & (array.length - 1)];
        head++;
        return value;
    }

    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        return array[head & (array.length - 1)];
    }

    @Override
    public boolean isEmpty() {
        return tail == head;
    }

    @Override
    public boolean isFull() {
        return tail - head == array.length;
    }
}
